package 力扣;

import java.util.ArrayList;
import java.util.List;

/**
 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

  

 示例：

 输入：n = 3
 输出：[
 "((()))",
 "(()())",
 "(())()",
 "()(())",
 "()()()"
 ]
 */
public class _22括号生成 {


    public List<String> generateParenthesis(int n) {

        ArrayList<String> ret = new ArrayList<>();
        backTrack("",0,0,n,ret);
        return ret;
    }

    private void backTrack(String s, int open, int close, int max, ArrayList<String> ret) {
        if( s.length() == 2 * max ){
            ret.add(s);
            return;
        }
        if( open < max){
            backTrack(s+"(",open+1,close,max,ret);
        }
        if( close < open){
            backTrack(s+")",open,close+1,max,ret);
        }
    }
}
